package com.ctwom.algorithm.questions.Csort;

/**
 * 快速排序
 * 思路：使用递归，每次以第一个元素为中界限节点M，让左边的数都小于中界限节点，右边的数都大于中界限节点。
 * 之后再把左L、右R两侧数据再以第一个元素为中界限节点...直到中界限到达左、右边界位置。
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {1,5,2,5,8,4,32,2};
        quickSort(arr, 0, arr.length-1);
        for(int i : arr){
            System.out.println(i);
        }
    }

    /**
     * 判断中止条件，如果边界位置到达右边界则中止，退回到上一次递归
     * @param arr 数组
     * @param L 左边界
     * @param R 右边界
     */
    public static void quickSort(int[] arr, int L, int R){
        int M = partition(arr, L, R);
        if(M == R){
            return;
        }
        quickSort(arr, L, M);
        quickSort(arr, M+1, R);
    }

    /**
     * 分区，每次以L元素为边界，比arr[L]小的放在arr[L]左侧，反之放在右侧
     * @param arr 数组
     * @param L 左边界
     * @param R 右边界
     * @return
     */
    public static int partition(int[] arr, int L, int R) {
        int part = arr[L];
        int partPos = L;
        int cursor = L+1;
        while(cursor <= R){
            if(part >= arr[cursor]){
                int change = arr[cursor];
                for(int i = cursor; i > partPos; i--){
                    arr[i] = arr[i-1];
                }
                arr[partPos] = change;
                partPos++;

            }
            cursor++;
        }
        return partPos;
    }
}
